package sample.xiaosong.violentrecursion;

/**
 * 给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值。
 * 给定一个正数bag，表示一个载重bag的袋子，你装的物 品不能超过这个重量。
 * 返回你能装下最多的价值是多少？
 */
public class Knapsack {

    public static int getMaxValue(int[] weights, int[] values, int bag) {
        return process(weights, values, 0, bag, 0);
    }

    /**
     * 对于每一次取舍，只需要比较要当前物品，和不要当前物品的大小即可
     * @param weights 重量
     * @param values 价值
     * @param i 第i个物品
     * @param bag 包的最大重量
     * @param selectedWeight 已经加入包中的重量
     * @return 最对能装的价值
     */
    public static int process(int[] weights, int[] values, int i, int bag, int selectedWeight) {
        if (selectedWeight > bag) {
            return 0;
        }
        if (i == weights.length) {
            return 0;
        }

        return Math.max(process(weights, values, i + 1, bag, selectedWeight),
                values[i] + process(weights, values, i + 1, bag, weights[i] + selectedWeight));
    }

    public static void main(String[] args) {
        int[] weights = { 3, 2, 4, 7 };
        int[] values = { 5, 6, 3, 19 };
        int bag = 11;
        System.out.println(getMaxValue(weights, values, bag));
    }
}
